package com.kk.datastructure.tree.foundactiontree;

/**
 * title: 线索化二叉树前中后序实现+遍历
 * @author 阿K
 * 2021年1月2日 上午2:05:23 
 */
public class ThreadedBinaryTreeDemo {

	public static void main(String[] args) {
		// 测试一把中序线索二叉树的功能
		HeroNode root = new HeroNode(1, "tom");
		HeroNode node2 = new HeroNode(3, "jack");
		HeroNode node3 = new HeroNode(6, "smith");
		HeroNode node4 = new HeroNode(8, "mary");
		HeroNode node5 = new HeroNode(10, "king");
		HeroNode node6 = new HeroNode(14, "dim");

		// 二叉树，后面我们要递归创建, 现在简单处理使用手动创建
		root.setLeft(node2);
		root.setRight(node3);
		node2.setLeft(node4);
		node2.setRight(node5);
		node3.setLeft(node6);
		// 后序专属：为节点手动绑定父节点
		node4.setParent(node2);
		node5.setParent(node2);
		node6.setParent(node3);
		node2.setParent(root);
		node3.setParent(root);

		// 测试中序线索化
		ThreadedBinaryTree threadedBinaryTree = new ThreadedBinaryTree();
		threadedBinaryTree.setRoot(root);
		// threadedBinaryTree.threadedNodes();
		// threadedBinaryTree.perThreadedNodes();
		threadedBinaryTree.postThreadedNodes();

		// 测试: 以10号节点测试
		HeroNode leftNode = node5.getLeft();
		HeroNode rightNode = node5.getRight();
		System.out.println("10号结点的前驱结点是 =" + leftNode); // 3
		System.out.println("10号结点的后继结点是=" + rightNode); // 1

		// 测试中序线索化遍历
		System.out.println("-------美丽的分割线------------");
		// threadedBinaryTree.threadedList();// 8,3,10,1,14,6

		// 测试前序线索化遍历
		System.out.println("-------美丽的分割线------------");
		// threadedBinaryTree.perThreadedList();// 1,3,8,10,6,14

		// 测试前序线索化遍历
		System.out.println("-------美丽的分割线------------");
		threadedBinaryTree.postThreadedList();// 8,10,3,14,6,1
	}
}

// 实现线索化二叉树
class ThreadedBinaryTree {

	private HeroNode root;

	public void setRoot(HeroNode root) {
		this.root = root;
	}

	// 重载方便调用
	public void threadedNodes() {
		this.threadedNodes(root);
	}

	// 重载方便调用
	public void perThreadedNodes() {
		this.perThreadedNodes(root);
	}

	// 重载方便调用
	public void postThreadedNodes() {
		this.postThreadedNodes(root);
	}

	// 1. 要实现线索化，需要一个指向当前节点的前驱节点
	// 2. 在递归进行线索化时， per 总是指向(保留)前一个节点
	public HeroNode per = null;

	// 遍历中序线索化二叉树 Api(中序线索化得用中序线索化遍历，前后序也如此)
	public void threadedList() {
		// 定义一个变量，存储当前遍历的结点，从root开始
		HeroNode node = root;
		while (node != null) {
			// 循环的找到 前驱节点(leftType ==1),第一个被找到的是 节点 8
			// 后面随着遍历而变化，因为当 leftType ==1时，说明该节点是按照线索化分布处理
			while (node.getLeftType() == 0) {
				// 若不是前驱则移动，知道才满足退出
				node = node.getLeft();
			}

			// 满足线索化，输出
			System.out.println(node);
			// 若当前节点的右指针指向的是后继节点，就一直输出
			while (node.getRightType() == 1) {
				// 获取当前节点的后继节点
				node = node.getRight();
				System.out.println(node);
			}
			// 替换当前遍历的节点（后移）---就像链表，缺少则是死循环
			node = node.getRight();
		}
	}

	// 遍历前序线索化二叉树 Api(按照后继搜索遍历)
	public void perThreadedList() {
		// 定义一个变量，存储当前遍历的结点，从root开始
		HeroNode node = root;// 此处 root 也可传参进来
		while (node != null) {

			while (node.getLeftType() == 0) {
				System.out.println(node);
				// 若不是前驱则移动
				node = node.getLeft();
			}
			System.out.println(node);
			// 替换当前遍历的节点（后移）---就像链表，缺少则是死循环
			node = node.getRight();
		}
	}

	// 遍历后序线索化二叉树 Api(按照后继)
	public void postThreadedList() {
		// 定义一个变量，存储当前遍历的结点，从root开始
		HeroNode node = root;
		while (node != null && node.getLeftType() == 0) {
			// 若不是前驱则移动，直到才满足退出
			node = node.getLeft();
		}

		// 辅助变量
		HeroNode perNode = null;

		while (node != null) {
			// 右节点是线索
			if (node.getRightType() == 1) {
				System.out.println(node);
				perNode = node;
				node = node.getRight();
			} else {
				// 若上个处理的节点，是当前节点的右节点
				if (node.getRight() == perNode) {
					System.out.println(node);
					if (node == root)
						return;

					// 往上移动
					perNode = node;
					node = node.getParent();

				} else {
					// 若从左节点的进入，则找到右子树的最左节点
					node = node.getRight();
					while (node != null && node.getLeftType() == 0) {
						node = node.getLeft();
					}
				}
			}
		}
	}

	// 二叉树进行中序线索化二叉树实现 Api
	public void threadedNodes(HeroNode node) {
		// 日常判空
		if (node == null) {
			return;
		}

		/**
		 * 个人理解：若没有左子树指向，即为空指向，若是左空，则指向前驱，若是右空，则指向后驱
		 */

		// 一、先线索化左子树
		threadedNodes(node.getLeft());

		// 二、线索化当前节点【难】
		// 1、处理当前节点的前驱节点
		// 举例：如上图的叶子节点 8 为例
		// 若节点 8.left == null（既没有左子树可指向，则指向前驱节点）, 节点 8.leftType =1(指定为前驱类型标识)
		if (node.getLeft() == null) {
			// 让当前节点的左指针，指向前驱节点
			node.setLeft(per);
			// 修改当前节点做指针的类型，定义为前驱
			node.setLeftType(1);
		}
		// 2、处理当前节点的后继节点(后继：就是在后面还得继续当前节点，所以还是这个节点在处理
		if (per != null && per.getRight() == null) {
			// 让前驱节点的右指针指向当前节点
			per.setRight(node);
			// 修改前驱节点的有指针类型
			per.setRightType(1);
		}
		// 每处理一个节点，让当前节点是下一个节点的前驱节点(后移)
		per = node;

		// 三、线索化右子树
		threadedNodes(node.getRight());
	}

	// 二叉树进行前序线索化二叉树实现 Api
	public void perThreadedNodes(HeroNode node) {
		// 日常判空
		if (node == null) {
			return;
		}

		/**
		 * 个人理解：若没有左子树指向，即为空指向，若是左空，则指向前驱，若是右空，则指向后驱 补充：若
		 * 是前序，递归语句在后面，则需要判断，中，后序只需要调整位置即可
		 */

		// 一、线索化当前节点
		// 1.左指针为空，将要左指针指向前驱节点
		if (node.getLeft() == null) {
			// 让当前节点的左指针，指向前驱节点
			node.setLeft(per);
			// 修改当前节点做指针的类型，定义为前驱
			node.setLeftType(1);
		}
		// 2.前一个节点的后继节点指向当前节点
		if (per != null && per.getRight() == null) {
			// 让前驱节点的右指针指向当前节点
			per.setRight(node);
			// 修改前驱节点的有指针类型
			per.setRightType(1);
		}
		// 每处理一个节点，让当前节点是下一个节点的前驱节点(后移)
		per = node;

		// 二、线索化左子树
		if (node.getLeftType() == 0)
			perThreadedNodes(node.getLeft());

		// 三、线索化右子树
		if (node.getRightType() == 0)
			perThreadedNodes(node.getRight());
	}

	// 二叉树进行后序线索化二叉树实现 Api
	public void postThreadedNodes(HeroNode node) {
		// 日常判空
		if (node == null) {
			return;
		}
		// 一、线索化左子树
		postThreadedNodes(node.getLeft());

		// 二、线索化右子树
		postThreadedNodes(node.getRight());

		// 三、线索化当前节点【难】
		// 1、处理当前节点的前驱节点
		// 举例：如上图的叶子节点 8 为例
		// 若节点 8.left == null（既没有左子树可指向，则指向前驱节点）, 节点 8.leftType =1(指定为前驱类型标识)
		if (node.getLeft() == null) {
			// 让当前节点的左指针，指向前驱节点
			node.setLeft(per);
			// 修改当前节点做指针的类型，定义为前驱
			node.setLeftType(1);
		}
		// 2、处理当前节点的后继节点(后继：就是在后面还得继续当前节点，所以还是这个节点在处理
		if (per != null && per.getRight() == null) {
			// 让前驱节点的右指针指向当前节点
			per.setRight(node);
			// 修改前驱节点的有指针类型
			per.setRightType(1);
		}
		// 每处理一个节点，让当前节点是下一个节点的前驱节点(后移)
		per = node;
	}
}

// 节点
class HeroNode {
	private int id;
	private String name;
	private HeroNode left;// 默认为 null
	private HeroNode right;// 默认为 null
	private HeroNode parent;// 父节点指针，为后序线索化使用

	// 说明：
	// 1、若 leftType == 0,表指向的是左子树；若 leftType ==1 ,表指向的是前驱节点
	// 2、若 rightType == 0,表指向的是右子树；若 leftType ==1 ,表指向的是后驱节点
	private int leftType;// 默认 0
	private int rightType;

	public HeroNode(int id, String name) {
		super();
		this.id = id;
		this.name = name;
	}

	public int getId() {
		return id;
	}

	public void setId(int id) {
		this.id = id;
	}

	public String getName() {
		return name;
	}

	public void setName(String name) {
		this.name = name;
	}

	public HeroNode getLeft() {
		return left;
	}

	public void setLeft(HeroNode left) {
		this.left = left;
	}

	public HeroNode getRight() {
		return right;
	}

	public void setRight(HeroNode right) {
		this.right = right;
	}

	public int getLeftType() {
		return leftType;
	}

	public void setLeftType(int leftType) {
		this.leftType = leftType;
	}

	public int getRightType() {
		return rightType;
	}

	public void setRightType(int rightType) {
		this.rightType = rightType;
	}

	public HeroNode getParent() {
		return parent;
	}

	public void setParent(HeroNode parent) {
		this.parent = parent;
	}

	@Override
	public String toString() {
		return "HeroNode [id=" + id + ", name=" + name + "]";
	}
}